import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MergeTwoSortedLists {


    /*
    将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

        List<Integer> lists = new ArrayList<>();
        while (list1!=null){
            lists.add(list1.val);
            list1 = list1.next;
        }
        while (list2!=null){
            lists.add(list2.val);
            list2 = list2.next;
        }
        if (lists.size()==0){
            return null;
        }

        int[] arr = new int[lists.size()];
        for (int i=0;i<arr.length;i++){
            arr[i] = lists.get(i);
        }

        Arrays.sort(arr);
        ListNode listNode = new ListNode(arr[0]);
        ListNode head = listNode;
        for (int i=1;i<arr.length;i++){
            ListNode temp_node = new ListNode(arr[i]);
            listNode.next =temp_node;
            listNode = listNode.next;
        }
        return head;

    }

    public static void main(String[] args) {


    }
}
